#include <bits/stdc++.h>

using namespace std;

// 路径总和 III
// 给定一个二叉树的根节点 root ，和一个整数 targetSum
// 求该二叉树里节点值之和等于 targetSum 的 路径 的数目
// 路径 不需要从根节点开始，也不需要在叶子节点结束
// 但是路径方向必须是向下的（只能从父节点到子节点）
// 测试链接 : https://leetcode.cn/problems/path-sum-iii/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    int ans;

	// sum : 从头节点出发，来到x的时候，上方累加和是多少
	// 路径必须以x作为结尾，路径累加和是target的路径数量，累加到全局变量ans上
    void f(TreeNode* x, int target, long sum, unordered_map<long, int>& presum)
    {
        if(x == nullptr) return;

        // 从头节点出发一路走到x的整体累加和
        sum += x->val;
        ans += presum[sum - target];
        ++presum[sum];
        f(x->left, target, sum, presum);
        f(x->right, target, sum, presum);
        --presum[sum];
    }

public:
    int pathSum(TreeNode* root, int target) 
    {
        unordered_map<long, int> presum;
        presum[0] = 1;
        ans = 0;
        f(root, target, 0, presum);
        return ans;
    }
};